package com.algorithm.learning.base.链表;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/19 22:49
 **/
public class 单链表 {

    public static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);

        Node node = reverseLinkedList(node1);
        while (node != null) {
            System.out.println(node.value);
            node = node.next;
        }
    }

    /**
     * 链表反转
     *
     * head -> node1 -> node2 -> node3 -> null, 要注意这里的head只是标识，其实就是node1
     * 我们按照下面的while循环步骤走一遍
     *
     * 首先定义两个变量 pre=null, next=null
     *
     * 第一次遍历开始
     * next = head.next = node1.next = node2
     *      => next = nod2
     * head.next = node1.next = pre = null
     *      => node1.next = null
     * pre = head
     *      => pre = node1
     * head = next
     *      => head = node2
     * 第一次遍历结果
     * null <- node1 <- pre  head->node2
     *
     * 第二次遍历开始
     * next = head.next = node2.next
     *      => node2.next = node3
     * head.next = pre
     *      => node2.next -> node1
     * pre = head(node2)
     *      => pre = node2
     * head = next(node3)
     *      => head -> node3
     * 第二次遍历结果
     * null <- node1 <- node2 <- pre  node3 <- head
     *
     * 第三次遍历开始
     * next = head.next = node3.next
     *      => next = null
     * head.next(node3.next) = pre = node2
     *      => node3.next = node2
     * pre = head(node3)
     *      => pre = node3
     * head = next(null)
     *      => head = null
     * 第三次遍历结果
     * null <- node1 <- node2 <- node3 <- pre  (head -> null, next -> null)
     * 这样正好可以得到反转的链表，最后的结果一定是pre作为head指向node3，而next与原head指向null
     * @param head
     * @return
     */
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            // 先记录next
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}
